package class05_归并排序练习题快排.test;

public class Code01_CountOfRangeSum {
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,1,55,6,9};
        countRangeSum(arr,1,3);
    }
    public static int countRangeSum(int[] arr, int lower, int upper){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }

        return process(sum, 0, arr.length - 1, lower, upper);
    }

    private static int process(int[] sum, int L, int R, int lower, int upper) {
        if(L == R){
            if(sum[L] >= lower && sum[L] <= upper){
                return 1;
            }else {
                return 0;
            }
        }

        int mid = L + ((R - L) >> 1);

        return
        process(sum, L, mid, lower, upper)
                +
        process(sum, mid + 1, R, lower, upper)
                +
        merge(sum, L, mid, R, lower, upper);
    }

    private static int merge(int[] sum, int L, int mid, int R, int lower, int upper) {

        int countRangeSum = 0;

        for (int i = mid + 1; i < R; i++) {
            int windowsL = sum[i] - upper;
            int windowsR = sum[i] - lower;
            int l = L;
            while (l <= mid){
                if(windowsL <= sum[l] && windowsR >= sum[l] ) {
                    countRangeSum++;
                }
                l++;
            }
        }


        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= R){
            help[index++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }
        while (p1 <= mid){
            help[index++] = sum[p1++];
        }
        while (p2 <= R){
            help[index++] = sum[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            sum[i + L] = help[i];
        }
        return countRangeSum;
    }
}
